#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/***************************************************************
 *函数名称：help_G
 *函数功能：图的功能菜单
 *返回值类型：void
 ****************************************************************/
void help_G(void) {
    printf("    1:创建图\n");
    printf("    2:销毁图\n");
    printf("    3:查找顶点\n");
    printf("    4:顶点赋值\n");
    printf("    5:查找第一邻接点\n");
    printf("    6:查找下一邻接点\n");
    printf("    7:插入顶点\n");
    printf("    8:删除顶点\n");
    printf("    9:插入弧\n");
    printf("    10:删除弧\n");
    printf("    11:深度优先搜索\n");
    printf("    12:广度优先搜索\n");
    printf("    13:图写入文件\n");
    printf("    14:图读取文件\n");
    printf("    15:距离小于k的顶点和\n");
    printf("    16:图的连通分量个数\n");
    printf("    17:遍历邻接表\n");
    printf("    18:菜单\n");
    printf("    0:退出\n");
}

/****************************************
 *函数功能：多表的功能菜单
 *返回值类型：void
 ****************************************************************/
void help_list(void) {
    printf("    1:创建一个邻接表\n");
    printf("    2:删除一个邻接表\n");
    printf("    3:查找一个邻接表\n");
    printf("    4:菜单\n");
    printf("    0:退出\n");
}

/***************************************************************
 *函数名称：CreateCraph
 *函数功能：根据V和VR构造图T并返回OK，如果V和VR不正确，返回ERROR如果有相同的关键字，返回ERROR。
 *返回值类型：status
 ****************************************************************/
status CreateCraph(ALGraph &G, VertexType V[], KeyType VR[][2]) {
    int len1 = 0, len2 = 0;
    while (V[len1].key != -1)
        len1++;
    if (len1 > MAX_VERTEX_NUM)
        return ERROR;
    while (VR[len2][0] != -1)
        len2++;
    if (!len1) {
        return ERROR;
    }
    G.kind = UDG;
    G.vexnum = len1;
    G.arcnum = 0;
    for (int i = 0; i < len1; i++) {
        G.vertices[i].data.key = V[i].key;
        strcpy(G.vertices[i].data.others, V[i].others);
        G.vertices[i].firstarc = NULL;
    }
    ArcNode *np, *nq;
    int i, j, k;
    for (i = 0; i < len2; i++) {
        for (j = 0; j < len1; j++) {
            if (G.vertices[j].data.key == VR[i][0]) {
                break;
            }
        }
        if (j == len1)
            return ERROR;
        for (k = 0; k < len1; k++) {
            if (G.vertices[k].data.key == VR[i][1])
                break;
        }
        if (k == len1)
            return ERROR;
        np = (ArcNode *)malloc(sizeof(ArcNode)); //采用前插法创建边结点
        np->adjvex = k;
        np->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = np;
        nq = (ArcNode *)malloc(sizeof(ArcNode));
        nq->adjvex = j;
        nq->nextarc = G.vertices[k].firstarc;
        G.vertices[k].firstarc = nq;
        G.arcnum++;
    }
    return OK;
}

/***************************************************************
 *函数名称：DestroyGraph
 *函数功能：销毁无向图G,删除G的全部顶点和边
 *返回值类型：status
 ****************************************************************/
status DestroyGraph(ALGraph &G) {
    ArcNode *p, *q;
    int num = G.vexnum;
    if (G.vexnum == 0)
        return INFEASIBLE;
    int nums = G.arcnum;
    for (int i = 0; i < num; i++) {
        p = G.vertices[i].firstarc;
        while (p) {
            q = p->nextarc;
            free(p);
            p = q;
            G.arcnum--;
        }
        G.vertices[i].firstarc = NULL;
        G.vexnum--;
    }
    G.arcnum += nums;
    return OK;
}

/***************************************************************
 *函数名称：LocateVex
 *函数功能：根据u在图G中查找顶点，查找成功返回位序，否则返回-1；
 *返回值类型：int
 ****************************************************************/
int LocateVex(ALGraph G, KeyType u) {
    int i;
    for (i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data.key == u) {
            return i;
        }
    }
    return -1;
}

/***************************************************************
 *函数名称：PutVex
 *函数功能：根据u在图G中查找顶点，查找成功将该顶点值修改成value，返回OK如果查找失败或关键字不唯一，返回ERROR
 *返回值类型：status
 ****************************************************************/
status PutVex(ALGraph &G, KeyType u, VertexType value) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data.key == value.key)
            return ERROR;
    }
    int i = 0;
    for (i; i < G.vexnum; i++) {
        if (G.vertices[i].data.key == u) {
            G.vertices[i].data.key = value.key;
            strcpy(G.vertices[i].data.others, value.others);
            return OK;
        }
    }
    return ERROR;
}

/***************************************************************
 *函数名称：FirstAdjVex
 *函数功能：根据u在图G中查找顶点，查找成功返回顶点u的第一邻接顶点位序，否则返回-1；
 *返回值类型：int
 ****************************************************************/
int FirstAdjVex(ALGraph G, KeyType u) {
    int i = 0;
    for (i; i < G.vexnum; i++) {
        if (G.vertices[i].data.key == u) {
            break;
        }
    }
    if (i == G.vexnum)
        return -1;
    return G.vertices[i].firstarc->adjvex;
    /********** End **********/
}

/***************************************************************
 *函数名称：NextAdjVex
 *函数功能：根据u在图G中查找顶点，查找成功返回顶点v的邻接顶点相对于w的下一邻接顶点的位序，查找失败返回-1；
 *返回值类型：int
 ****************************************************************/
int NextAdjVex(ALGraph G, KeyType v, KeyType w) {
    ArcNode *p;
    int i = 0;
    for (i; i < G.vexnum; i++) {
        if (G.vertices[i].data.key == v) {
            break;
        }
    }
    if (i == G.vexnum)
        return -1;
    p = G.vertices[i].firstarc;
    while (p) {
        if (G.vertices[p->adjvex].data.key == w) {
            break;
        }
        p = p->nextarc;
    }
    if (p == NULL || p->nextarc == NULL)
        return -1;
    return p->nextarc->adjvex;
}

/***************************************************************
 *函数名称：InsertVex
 *函数功能：在图G中插入顶点v，成功返回OK,否则返回ERROR
 *返回值类型：status
 ****************************************************************/
status InsertVex(ALGraph &G, VertexType v) {
    if (G.vexnum == MAX_VERTEX_NUM)
        return ERROR;
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data.key == v.key)
            return ERROR;
    }
    G.vertices[G.vexnum].data.key = v.key;
    strcpy(G.vertices[G.vexnum].data.others, v.others);
    G.vertices[G.vexnum].firstarc = NULL;
    G.vexnum++;
    return OK;
}

/***************************************************************
 *函数名称：DeleteVex
 *函数功能：在图G中删除关键字v对应的顶点以及相关的弧，成功返回OK,否则返回ERROR
 *返回值类型：status
 ****************************************************************/
status DeleteVex(ALGraph &G, KeyType v) {
    int loc = -1;
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data.key == v) {
            loc = i;
            break;
        }
    }
    if (loc == -1)
        return ERROR;
    ArcNode *p, *q;
    int i = 0;
    for (i; i < G.vexnum; i++) {
        if (i == loc)
            continue;
        p = G.vertices[i].firstarc;
        if (p && p->adjvex == loc) {
            G.vertices[i].firstarc = p->nextarc;
            free(p);
        }
        p = G.vertices[i].firstarc;
        while (p) {
            q = p->nextarc;
            if (q && q->adjvex == loc) {
                p->nextarc = q->nextarc;
                free(q);
            }
            p = p->nextarc;
        }
    }
    while (G.vertices[loc].firstarc) {
        p = G.vertices[loc].firstarc;
        G.vertices[loc].firstarc = p->nextarc;
        if (p)
            free(p);
        G.arcnum--;
    }
    for (int i = loc; i < G.vexnum - 1; i++) {
        G.vertices[i].data.key = G.vertices[i + 1].data.key;
        strcpy(G.vertices[i].data.others, G.vertices[i + 1].data.others);
        G.vertices[i].firstarc = G.vertices[i + 1].firstarc;
    }
    G.vexnum--;
    if (!G.vexnum)
        return ERROR;
    for (i = 0; i < G.vexnum; i++) {
        ArcNode *p = G.vertices[i].firstarc;
        while (p) {
            if (p && p->adjvex > loc)
                p->adjvex--;
            p = p->nextarc;
        }
    }
    return OK;
}

/***************************************************************
 *函数名称：InsertArc
 *函数功能：在图G中增加弧<v,w>，成功返回OK,否则返回ERROR
 *返回值类型：status
 ****************************************************************/
status InsertArc(ALGraph &G, KeyType v, KeyType w) {
    int one = -1, two = -1;
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data.key == v) {
            one = i;
        }
        if (G.vertices[i].data.key == w) {
            two = i;
        }
    }
    if (one == -1 || two == -1)
        return ERROR;
    ArcNode *q = G.vertices[one].firstarc;
    while (q) {
        if (q->adjvex == two)
            return ERROR;
        q = q->nextarc;
    }
    ArcNode *p;
    p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = two;
    p->nextarc = G.vertices[one].firstarc;
    G.vertices[one].firstarc = p;
    p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = one;
    p->nextarc = G.vertices[two].firstarc;
    G.vertices[two].firstarc = p;
    G.arcnum++;
    return OK;
}

/***************************************************************
 *函数名称：DeleteArc
 *函数功能：在图G中删除弧<v,w>，成功返回OK,否则返回ERROR
 *返回值类型：status
 ****************************************************************/
status DeleteArc(ALGraph &G, KeyType v, KeyType w) {
    int one = -1, two = -1;
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data.key == v) {
            one = i;
        }
        if (G.vertices[i].data.key == w) {
            two = i;
        }
    }
    if (one == -1 || two == -1)
        return ERROR;
    int flag = 1;
    ArcNode *p, *q;
    p = G.vertices[one].firstarc;
    if (p && p->adjvex == two) {
        G.vertices[one].firstarc = p->nextarc;
        free(p);
    }
    p = G.vertices[one].firstarc;
    while (p) {
        q = p->nextarc;
        if (q && q->adjvex == two) {
            p->nextarc = q->nextarc;
            free(q);
            flag = 0;
            break;
        }
        p = p->nextarc;
    }
    p = G.vertices[two].firstarc;
    if (p && p->adjvex == one) {
        G.vertices[two].firstarc = p->nextarc;
        free(p);
    }
    p = G.vertices[two].firstarc;
    while (p) {
        q = p->nextarc;
        if (q && q->adjvex == one) {
            p->nextarc = q->nextarc;
            free(q);
            flag = 0;
            break;
        }
        p = p->nextarc;
    }
    G.arcnum--;
    if (flag)
        return ERROR;
    return OK;
}

void visit(VertexType v) {
    printf(" %d %s", v.key, v.others);
}

int DFSvisited[20] = {0};
status DFStravel(ALGraph &G, void (*visit)(VertexType), int i)
//深度优先搜索递归算法
{
    if (!DFSvisited[i]) {
        visit(G.vertices[i].data);
        DFSvisited[i] = 1;
        ArcNode *p;
        p = G.vertices[i].firstarc;
        while (p) {
            DFStravel(G, visit, p->adjvex);
            p = p->nextarc;
        }

    } else
        return OK;
    return OK;
}

/***************************************************************
 *函数名称：DFSTraverse
 *函数功能：对图G进行深度优先搜索遍历，依次对图中的每一个顶点使用函数visit访问一次，且仅访问一次
 *返回值类型：status
 ****************************************************************/
status DFSTraverse(ALGraph &G, void (*visit)(VertexType)) {
    if (G.vexnum == 0)
        return ERROR;
    memset(DFSvisited, 0, sizeof(DFSvisited));
    for (int i = 0; i < G.vexnum; i++)
        DFStravel(G, visit, i);
    return OK;
}

/***************************************************************
 *函数名称：BFSTraverse
 *函数功能：对图G进行广度优先搜索遍历，依次对图中的每一个顶点使用函数visit访问一次，且仅访问一次
 *返回值类型：status
 ****************************************************************/
status BFSTraverse(ALGraph &G, void (*visit)(VertexType)) {
    int BFSvisited[20] = {0};
    int ans = 0;
    int i = 0, j = 0;
    int list[20];
    list[0] = 0;
    j++;
    while (ans < G.vexnum) {
        if (i == j) {
            for (int loc = 0; loc < G.vexnum; loc++) {
                if (!BFSvisited[loc]) {
                    list[j++] = loc;
                    break;
                }
            }
        }
        while (i != j) {
            if (!BFSvisited[list[i]]) {
                visit(G.vertices[list[i]].data);
                ans++;
                BFSvisited[list[i]] = 1;
                ArcNode *p;
                p = G.vertices[list[i]].firstarc;
                while (p) {
                    list[j++] = p->adjvex;
                    p = p->nextarc;
                }
                i++;
            } else if (BFSvisited[list[i]])
                i++;
        }
    }
    return OK;
}

/***************************************************************
 *函数名称：SaveGraph
 *函数功能：将图的数据写入到文件FileName中
 *返回值类型：status
 ****************************************************************/
status SaveGraph(ALGraph G, char FileName[]) {
    FILE *fp;
    fp = fopen(FileName, "w");
    if (fp == NULL)
        return ERROR;
    ArcNode *p;
    ArcNode *list[100];
    int len = 0;
    for (int i = 0; i < G.vexnum; i++) {
        fprintf(fp, "%d %s ", G.vertices[i].data.key, G.vertices[i].data.others);
        p = G.vertices[i].firstarc;
        while (p) {
            list[len++] = p;
            p = p->nextarc;
        }
        while (len) {
            p = list[--len];
            fprintf(fp, "%d ", p->adjvex);
        }
        fprintf(fp, "%d ", -1);
    }
    fprintf(fp, "%d %s ", -1, "nil");
    fclose(fp);
    return OK;
}

/***************************************************************
 *函数名称： LoadGraph
 *函数功能：读入文件FileName的图数据，创建图的邻接表
 *返回值类型：status
 ****************************************************************/
status LoadGraph(ALGraph &G, char FileName[]) {
    G.vexnum = 0;
    G.arcnum = 0;
    FILE *fp;
    fp = fopen(FileName, "r");
    if (fp == NULL)
        return ERROR;
    VertexType V[21];
    KeyType VR[100][2];
    ArcNode *p;
    int i = 0, tem = 0;
    fscanf(fp, "%d %s ", &V[i].key, V[i].others);
    while (V[i].key != -1) {
        G.vertices[i].data.key = V[i].key;
        strcpy(G.vertices[i].data.others, V[i].others);
        G.vertices[i].firstarc = NULL;
        fscanf(fp, "%d ", &tem);
        while (tem != -1) {
            p = (ArcNode *)malloc(sizeof(ArcNode));
            p->adjvex = tem;
            p->nextarc = G.vertices[i].firstarc;
            G.vertices[i].firstarc = p;
            G.arcnum++;
            fscanf(fp, "%d ", &tem);
        }
        G.vexnum++;
        i++;
        fscanf(fp, "%d %s ", &V[i].key, V[i].others);
    }
    fclose(fp);
    G.arcnum /= 2;
    return OK;
}

/***************************************************************
 *函数名称： CreateLists
 *函数功能：创建一个多表命名为Filename
 *返回值类型：status
 ****************************************************************/
status CreateLists(LISTS &L, char Filrname[]) {
    if (L.length == MAX_VERTEX_NUM)
        return INFEASIBLE;
    strcpy(L.elem[L.length].name, Filrname);
    VertexType V[21];
    KeyType VR[100][2];
    printf("请输入数据\n");
    int i = 0;
    do {
        scanf("%d%s", &V[i].key, V[i].others);
    } while (V[i++].key != -1);
    i = 0;
    do {
        scanf("%d%d", &VR[i][0], &VR[i][1]);
    } while (VR[i++][0] != -1);
    i = CreateCraph(L.elem[L.length++].G, V, VR);
    if (i == ERROR)
        return ERROR;
    return OK;
}

/***************************************************************
 *函数名称：Deletelist
 *函数功能：删除一个多表中的名为Filename的图
 *返回值类型：status
 ****************************************************************/
status Deletelist(LISTS &L, char Filrname[]) {
    if (L.length == 0)
        return INFEASIBLE;
    int loc = -1;
    for (int i = 0; i < L.length; i++) {
        if (!strcmp(L.elem[i].name, Filrname)) {
            loc = i;
            break;
        }
    }
    if (loc == -1)
        return INFEASIBLE;
    for (int i = loc; i < L.length - 1; i++) {
        L.elem[i].G = L.elem[i + 1].G;
        strcpy(L.elem[i].name, L.elem[i + 1].name);
    }
    L.length--;
    return OK;
}

/***************************************************************
 *函数名称：Checklist
 *函数功能：在多表中查找一个名为Filename的图
 *返回值类型：int
 ****************************************************************/
int Checklist(LISTS &L, char Filename[]) {
    if (L.length == 0)
        return INFEASIBLE;
    int loc = -1;
    for (int i = 0; i < L.length; i++) {
        if (!strcmp(L.elem[i].name, Filename)) {
            loc = i;
            break;
        }
    }
    if (loc == -1)
        return INFEASIBLE;
    return loc;
}

int DFSVerticesSetLessThanKvisited[20];
int *L;
int len = 1;
int length = -1;
status DFSVerticesSetLessThanK(ALGraph &G, int i, int k) {
    length++;
    if (!DFSVerticesSetLessThanKvisited[i] && length < k) {
        L[len++] = i;
        DFSVerticesSetLessThanKvisited[i] = 1;
        ArcNode *p;
        p = G.vertices[i].firstarc;
        while (p) {
            DFSVerticesSetLessThanK(G, p->adjvex, k);
            p = p->nextarc;
        }
    }
    length--;
    return OK;
}

/***************************************************************
 *函数名称：VerticesSetLessThanK
 *函数功能：初始条件是图G存在；操作结果是返回与顶点v距离小于k的顶点集合；
 *返回值类型：int *
 ****************************************************************/
int *VerticesSetLessThanK(ALGraph G, KeyType v, int k) {
    if (G.vexnum == 0)
        return NULL;
    L = (int *)malloc(sizeof(int) * MAX_VERTEX_NUM);
    int loc = -1;
    len = 1;
    length = -1;
    memset(L, 0, sizeof(L));                                                           //初始化数组
    memset(DFSVerticesSetLessThanKvisited, 0, sizeof(DFSVerticesSetLessThanKvisited)); //初始化记录已访问过的结点的数组
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data.key == v) {
            loc = i;
            break;
        }
    }
    if (loc == -1)
        return ERROR;
    DFSVerticesSetLessThanK(G, loc, k);
    L[0] = len - 1;
    return L;
}

/***************************************************************
 *函数名称：ConnectedComponentsNums
 *函数功能：初始条件是图G存在；操作结果是返回图G的所有连通分量的个数；
 *返回值类型：int
 ****************************************************************/
int ConnectedComponentsNums(ALGraph G) {
    if (G.vexnum == 0)
        return INFEASIBLE;
    int len = 0;              //图的连通分量个数
    int BFSvisited[20] = {0}; //标记已遍历的顶点
    int ans = 0;
    int i = 0, j = 0;
    int list[20]; //创建一个队列
    list[0] = 0;
    j++;
    len++; //第一个顶点进队列图的连通分量增加
    while (ans < G.vexnum) {
        if (i == j) {
            len++; //图不连通此时连通分量增加，将下一个顶点进队列
            for (int loc = 0; loc < G.vexnum; loc++) {
                if (!BFSvisited[loc]) {
                    list[j++] = loc;
                    break;
                }
            }
        }
        while (i != j) {
            if (!BFSvisited[list[i]]) {
                ans++;
                BFSvisited[list[i]] = 1;
                ArcNode *p;
                p = G.vertices[list[i]].firstarc;
                while (p) {
                    list[j++] = p->adjvex;
                    p = p->nextarc;
                }
                i++;
            } else if (BFSvisited[list[i]])
                i++;
        }
    }
    return len;
}

/***************************************************************
 *函数名称：Gtravel
 *函数功能：遍历邻接表
 *返回值类型：status
 ****************************************************************/
status Gtravel(ALGraph G) {
    if (G.vexnum == 0)
        return ERROR;
    int i = 0;
    for (i = 0; i < G.vexnum; i++) {
        ArcNode *p = G.vertices[i].firstarc;
        printf("%d %s", G.vertices[i].data.key, G.vertices[i].data.others);
        while (p) {
            printf(" %d", p->adjvex);
            p = p->nextarc;
        }
        printf("\n");
    }
    return OK;
}